/**
 * Sizzle引擎
 */
(function(window, undefined) {

    var
        // 选择器缓存
        tokenCache = createCache(),
        compilerCache = createCache(),
        classCache = createCache(),

        booleans = "checked|selected|async|autofocus|autoplay|controls|defer|disabled|hidden|" +
            "ismap|loop|multiple|open|readonly|required|scoped",


        // 空白字符
        whitespace = "[\\x20\\t\\r\\n\\f]",

        // ClassName或ID Name
        identifier = "(?:\\\\[\\da-fA-F]{1,6}" + whitespace +
            "?|\\\\[^\\r\\n\\f]|[\\w-]|[^\0-\\x7f])+",

        // css选择器属性，如[type="phone"]
        attributes = "\\[" + whitespace + "*(" + identifier + ")(?:" + whitespace +

            // Operator (capture 2)
            "*([*^$|!~]?=)" + whitespace +

            // "Attribute values must be CSS identifiers [capture 5]
            // or strings [capture 3 or capture 4]"
            "*(?:'((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\"|(" + identifier + "))|)" +
            whitespace + "*\\]",

        pseudos = ":(" + identifier + ")(?:\\((" +

            // To reduce the number of selectors needing tokenize in the preFilter, prefer arguments:
            // 1. quoted (capture 3; capture 4 or capture 5)
            "('((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\")|" +

            // 2. simple (capture 6)
            "((?:\\\\.|[^\\\\()[\\]]|" + attributes + ")*)|" +

            // 3. anything else (capture 2)
            ".*" +
            ")\\)|)",

        // Leading and non-escaped trailing whitespace, capturing some non-whitespace characters preceding the latter
        rwhitespace = new RegExp( whitespace + "+", "g" ),

        // 去除左右空格用
        rtrim = new RegExp( "^" + whitespace + "+|((?:^|[^\\\\])(?:\\\\.)*)" +
            whitespace + "+$", "g" ),

        // 逗号
        rcomma = new RegExp( "^" + whitespace + "*," + whitespace + "*" ),

        // >, +, 空格, ~
        rcombinators = new RegExp( "^" + whitespace + "*([>+~]|" + whitespace + ")" + whitespace +
            "*" ),
        rdescend = new RegExp( whitespace + "|>" ),

        rpseudo = new RegExp( pseudos ),
        ridentifier = new RegExp( "^" + identifier + "$" ),

        matchExpr = {
            "ID": new RegExp( "^#(" + identifier + ")" ),
            "CLASS": new RegExp( "^\\.(" + identifier + ")" ),
            "TAG": new RegExp( "^(" + identifier + "|[*])" ),
            "ATTR": new RegExp( "^" + attributes ),
            "PSEUDO": new RegExp( "^" + pseudos ),
            "CHILD": new RegExp( "^:(only|first|last|nth|nth-last)-(child|of-type)(?:\\(" +
                whitespace + "*(even|odd|(([+-]|)(\\d*)n|)" + whitespace + "*(?:([+-]|)" +
                whitespace + "*(\\d+)|))" + whitespace + "*\\)|)", "i" ),
            "bool": new RegExp( "^(?:" + booleans + ")$", "i" ),

            // For use in libraries implementing .is()
            // We use this for POS matching in `select`
            "needsContext": new RegExp( "^" + whitespace +
                "*[>+~]|:(even|odd|eq|gt|lt|nth|first|last)(?:\\(" + whitespace +
                "*((?:-\\d)?\\d*)" + whitespace + "*\\)|)(?=[^-]|$)", "i" )
        },

        rhtml = /HTML$/i,
        rinputs = /^(?:input|select|textarea|button)$/i,
        rheader = /^h\d$/i,

        rnative = /^[^{]+\{\s*\[native \w/,

        // Easily-parseable/retrievable ID or TAG or CLASS selectors
        rquickExpr = /^(?:#([\w-]+)|(\w+)|\.([\w-]+))$/,

        rsibling = /[+~]/,

        // CSS escapes
        // http://www.w3.org/TR/CSS21/syndata.html#escaped-characters
        runescape = new RegExp( "\\\\[\\da-fA-F]{1,6}" + whitespace + "?|\\\\([^\\r\\n\\f])", "g" ),
        
        funescape = function( escape, nonHex ) {
            var high = "0x" + escape.slice( 1 ) - 0x10000;

            return nonHex ?

                // Strip the backslash prefix from a non-hex escape sequence
                nonHex :

                // Replace a hexadecimal escape sequence with the encoded Unicode code point
                // Support: IE <=11+
                // For values outside the Basic Multilingual Plane (BMP), manually construct a
                // surrogate pair
                high < 0 ?
                    String.fromCharCode( high + 0x10000 ) :
                    String.fromCharCode( high >> 10 | 0xD800, high & 0x3FF | 0xDC00 );
        };

    var Sizzle = function() {

    }

    Sizzle.tokenize = function (selector, parseOnly) {
        var matched,                        // 用于判断每执行一次while循环是否解析成功，如果为false说明css选择器有错误，直接终止循环
            match,                          // 正则匹配结果
            tokens,                         // Token序列
            soFar = selector,               // 表示字符串未解析的部分
            groups = [],                    // 存放已经解析好的Token序列
            preFilters = Expr.preFilter,    // 预处理用
            cached = tokenCache[selector];  // 缓存

        if (cached) {
            return parseOnly ? 0 : cached;
        }

        while (soFar) {

            // 第一大块，分组关系
            // 检查是否有逗号，有逗号的话就是多个Token序列
            // 比如像'div > p + .aaron[type="checkbox"], #id:first-child'这个选择器就是两个Token序列
            // groups = [
            //     [序列一],   // div > p + .aaron[type="checkbox"]
            //     [序列二]    // #id:first-child
            // ]
            if (!matched || (match = rcomma.exec(soFar))) {
                if (match) {
                    // 清除逗号
                    soFar = soFar.slice(match[0].length);
                }

                // 每有一个逗号，都要往groups压入一个Token序列
                // 然后就是最开始的时候也要往groups压入一个Token
                groups.push(tokens = []);
            }

            matched = false;

            // 第二大块，层级关系
            // 处理特殊的Token：>, +, 空格, ~
            if (match = rcombinators.exec(soFar)) {
                matched = match.shift();
                tokens.push({
                    value: matched,
                    type: match[0].replace(rtrim, " ")
                });

                // 处理完之后将其从待处理的字符中删除
                soFar = soFar.slice(matched.length);
            }

            // 第三大块，选择器
            // 这里开始分析这几种Token：TAG, ID, CLASS, ATTR, CHILD, PSEUDO, NAME
            // 如果通过正则匹配到了Token格式：match = matchExpr[ type ].exec( soFar )
            // 需要预处理的Token：ATTR, CHILD, PSEUDO
            // 交给预处理器处理：match = preFilters[ type ]( match )
            for (var type in Expr.filter) {
                if ( match = matchExpr[type].exec(soFar) ) {
                    // 预处理
                    if (preFilters[type]) {
                        match = preFilters[type](match);
                    }

                    matched = match.shift();
                    tokens.push({
                        value: matched,
                        type: type,
                        matches: match
                    })

                    // 处理完之后将其从待处理的字符中删除
                    soFar = soFar.slice(matched.length);
                }
            }

            // 如果到了这里都还没matched到，那么说明这个选择器在这里有错误
            // 直接中断词法分析过程
            // 这就是Sizzle对词法分析的异常处理
            if (!matched) {
                break;
            }
        }

        // 如果只需要这个接口检查选择器的合法性，直接就返回soFar的剩余长度，因为soFar长度大于零说明选择器不合法
        // 其余情况，如果soFar不等于""，抛出异常；否则把groups记录在cache里边并返回
        return parseOnly ?
            soFar.length :
            soFar ?
                Sizzle.error(selector) :

                // 这里对选择器(selector)做一个缓存
                tokenCache(selector, groups);
    }

    var Expr = Sizzle.selectors = {

        // 选择器缓存长度
        cacheLength: 50,

        // 查询seed集合用
        find: {

            "ID": function( id ) {
                var elem = document.getElementById( id );
                return elem ? [ elem ] : [];
            },

            "TAG": function( tag ) {
                return document.getElementsByTagName( tag );
            },

            "CLASS": function ( className ) {
                return document.getElementsByClassName( className );
            }
        },

        // 位置词素
        relative: {
            ">": { dir: "parentNode", first: true },
            " ": { dir: "parentNode" },
            "+": { dir: "previousSibling", first: true },
            "~": { dir: "previousSibling" }
        },

        // 预处理
        preFilter: {
            "ATTR": function( match ) {
                match[ 1 ] = match[ 1 ].replace( runescape, funescape );

                // Move the given value to match[3] whether quoted or unquoted
                match[ 3 ] = ( match[ 3 ] || match[ 4 ] ||
                    match[ 5 ] || "" ).replace( runescape, funescape );

                if ( match[ 2 ] === "~=" ) {
                    match[ 3 ] = " " + match[ 3 ] + " ";
                }

                return match.slice( 0, 4 );
            },

            "CHILD": function( match ) {

                /* matches from matchExpr["CHILD"]
                    1 type (only|nth|...)
                    2 what (child|of-type)
                    3 argument (even|odd|\d*|\d*n([+-]\d+)?|...)
                    4 xn-component of xn+y argument ([+-]?\d*n|)
                    5 sign of xn-component
                    6 x of xn-component
                    7 sign of y-component
                    8 y of y-component
                */
                match[ 1 ] = match[ 1 ].toLowerCase();

                if ( match[ 1 ].slice( 0, 3 ) === "nth" ) {

                    // nth-* requires argument
                    if ( !match[ 3 ] ) {
                        Sizzle.error( match[ 0 ] );
                    }

                    // numeric x and y parameters for Expr.filter.CHILD
                    // remember that false/true cast respectively to 0/1
                    match[ 4 ] = +( match[ 4 ] ?
                        match[ 5 ] + ( match[ 6 ] || 1 ) :
                        2 * ( match[ 3 ] === "even" || match[ 3 ] === "odd" ) );
                    match[ 5 ] = +( ( match[ 7 ] + match[ 8 ] ) || match[ 3 ] === "odd" );

                    // other types prohibit arguments
                } else if ( match[ 3 ] ) {
                    Sizzle.error( match[ 0 ] );
                }

                return match;
            },

            "PSEUDO": function( match ) {
                var excess,
                    unquoted = !match[ 6 ] && match[ 2 ];

                if ( matchExpr[ "CHILD" ].test( match[ 0 ] ) ) {
                    return null;
                }

                // Accept quoted arguments as-is
                if ( match[ 3 ] ) {
                    match[ 2 ] = match[ 4 ] || match[ 5 ] || "";

                    // Strip excess characters from unquoted arguments
                } else if ( unquoted && rpseudo.test( unquoted ) &&

                    // Get excess from tokenize (recursively)
                    ( excess = tokenize( unquoted, true ) ) &&

                    // advance to the next closing parenthesis
                    ( excess = unquoted.indexOf( ")", unquoted.length - excess ) - unquoted.length ) ) {

                    // excess is a negative index
                    match[ 0 ] = match[ 0 ].slice( 0, excess );
                    match[ 2 ] = unquoted.slice( 0, excess );
                }

                // Return only captures needed by the pseudo filter method (type and argument)
                return match.slice( 0, 3 );
            }
        },

        // 匹配器
        filter: {

            "TAG": function( nodeNameSelector ) {
                var nodeName = nodeNameSelector.replace( runescape, funescape ).toLowerCase();
                return nodeNameSelector === "*" ?
                    function() {
                        return true;
                    } :
                    function( elem ) {
                        return elem.nodeName && elem.nodeName.toLowerCase() === nodeName;
                    };
            },

            "CLASS": function( className ) {
                var pattern = classCache[ className + " " ];

                return pattern ||
                    ( pattern = new RegExp( "(^|" + whitespace +
                        ")" + className + "(" + whitespace + "|$)" ) ) && classCache(
                        className, function( elem ) {
                            return pattern.test(
                                typeof elem.className === "string" && elem.className ||
                                typeof elem.getAttribute !== "undefined" &&
                                elem.getAttribute( "class" ) ||
                                ""
                            );
                        } );
            },

            "ATTR": function( name, operator, check ) {
                return function( elem ) {
                    var result = Sizzle.attr( elem, name );

                    if ( result == null ) {
                        return operator === "!=";
                    }
                    if ( !operator ) {
                        return true;
                    }

                    result += "";

                    /* eslint-disable max-len */

                    return operator === "=" ? result === check :
                        operator === "!=" ? result !== check :
                            operator === "^=" ? check && result.indexOf( check ) === 0 :
                                operator === "*=" ? check && result.indexOf( check ) > -1 :
                                    operator === "$=" ? check && result.slice( -check.length ) === check :
                                        operator === "~=" ? ( " " + result.replace( rwhitespace, " " ) + " " ).indexOf( check ) > -1 :
                                            operator === "|=" ? result === check || result.slice( 0, check.length + 1 ) === check + "-" :
                                                false;
                    /* eslint-enable max-len */

                };
            },

            "CHILD": function( type, what, _argument, first, last ) {
                var simple = type.slice( 0, 3 ) !== "nth",
                    forward = type.slice( -4 ) !== "last",
                    ofType = what === "of-type";

                return first === 1 && last === 0 ?

                    // Shortcut for :nth-*(n)
                    function( elem ) {
                        return !!elem.parentNode;
                    } :

                    function( elem, _context, xml ) {
                        var cache, uniqueCache, outerCache, node, nodeIndex, start,
                            dir = simple !== forward ? "nextSibling" : "previousSibling",
                            parent = elem.parentNode,
                            name = ofType && elem.nodeName.toLowerCase(),
                            useCache = !xml && !ofType,
                            diff = false;

                        if ( parent ) {

                            // :(first|last|only)-(child|of-type)
                            if ( simple ) {
                                while ( dir ) {
                                    node = elem;
                                    while ( ( node = node[ dir ] ) ) {
                                        if ( ofType ?
                                            node.nodeName.toLowerCase() === name :
                                            node.nodeType === 1 ) {

                                            return false;
                                        }
                                    }

                                    // Reverse direction for :only-* (if we haven't yet done so)
                                    start = dir = type === "only" && !start && "nextSibling";
                                }
                                return true;
                            }

                            start = [ forward ? parent.firstChild : parent.lastChild ];

                            // non-xml :nth-child(...) stores cache data on `parent`
                            if ( forward && useCache ) {

                                // Seek `elem` from a previously-cached index

                                // ...in a gzip-friendly way
                                node = parent;
                                outerCache = node[ expando ] || ( node[ expando ] = {} );

                                // Support: IE <9 only
                                // Defend against cloned attroperties (jQuery gh-1709)
                                uniqueCache = outerCache[ node.uniqueID ] ||
                                    ( outerCache[ node.uniqueID ] = {} );

                                cache = uniqueCache[ type ] || [];
                                nodeIndex = cache[ 0 ] === dirruns && cache[ 1 ];
                                diff = nodeIndex && cache[ 2 ];
                                node = nodeIndex && parent.childNodes[ nodeIndex ];

                                while ( ( node = ++nodeIndex && node && node[ dir ] ||

                                    // Fallback to seeking `elem` from the start
                                    ( diff = nodeIndex = 0 ) || start.pop() ) ) {

                                    // When found, cache indexes on `parent` and break
                                    if ( node.nodeType === 1 && ++diff && node === elem ) {
                                        uniqueCache[ type ] = [ dirruns, nodeIndex, diff ];
                                        break;
                                    }
                                }

                            } else {

                                // Use previously-cached element index if available
                                if ( useCache ) {

                                    // ...in a gzip-friendly way
                                    node = elem;
                                    outerCache = node[ expando ] || ( node[ expando ] = {} );

                                    // Support: IE <9 only
                                    // Defend against cloned attroperties (jQuery gh-1709)
                                    uniqueCache = outerCache[ node.uniqueID ] ||
                                        ( outerCache[ node.uniqueID ] = {} );

                                    cache = uniqueCache[ type ] || [];
                                    nodeIndex = cache[ 0 ] === dirruns && cache[ 1 ];
                                    diff = nodeIndex;
                                }

                                // xml :nth-child(...)
                                // or :nth-last-child(...) or :nth(-last)?-of-type(...)
                                if ( diff === false ) {

                                    // Use the same loop as above to seek `elem` from the start
                                    while ( ( node = ++nodeIndex && node && node[ dir ] ||
                                        ( diff = nodeIndex = 0 ) || start.pop() ) ) {

                                        if ( ( ofType ?
                                            node.nodeName.toLowerCase() === name :
                                            node.nodeType === 1 ) &&
                                            ++diff ) {

                                            // Cache the index of each encountered element
                                            if ( useCache ) {
                                                outerCache = node[ expando ] ||
                                                    ( node[ expando ] = {} );

                                                // Support: IE <9 only
                                                // Defend against cloned attroperties (jQuery gh-1709)
                                                uniqueCache = outerCache[ node.uniqueID ] ||
                                                    ( outerCache[ node.uniqueID ] = {} );

                                                uniqueCache[ type ] = [ dirruns, diff ];
                                            }

                                            if ( node === elem ) {
                                                break;
                                            }
                                        }
                                    }
                                }
                            }

                            // Incorporate the offset, then check against cycle size
                            diff -= last;
                            return diff === first || ( diff % first === 0 && diff / first >= 0 );
                        }
                    };
            },

            "PSEUDO": function( pseudo, argument ) {

                // pseudo-class names are case-insensitive
                // http://www.w3.org/TR/selectors/#pseudo-classes
                // Prioritize by case sensitivity in case custom pseudos are added with uppercase letters
                // Remember that setFilters inherits from pseudos
                var args,
                    fn = Expr.pseudos[ pseudo ] || Expr.setFilters[ pseudo.toLowerCase() ] ||
                        Sizzle.error( "unsupported pseudo: " + pseudo );

                // The user may use createPseudo to indicate that
                // arguments are needed to create the filter function
                // just as Sizzle does
                if ( fn[ expando ] ) {
                    return fn( argument );
                }

                // But maintain support for old signatures
                if ( fn.length > 1 ) {
                    args = [ pseudo, pseudo, "", argument ];
                    return Expr.setFilters.hasOwnProperty( pseudo.toLowerCase() ) ?
                        markFunction( function( seed, matches ) {
                            var idx,
                                matched = fn( seed, argument ),
                                i = matched.length;
                            while ( i-- ) {
                                idx = indexOf( seed, matched[ i ] );
                                seed[ idx ] = !( matches[ idx ] = matched[ i ] );
                            }
                        } ) :
                        function( elem ) {
                            return fn( elem, 0, args );
                        };
                }

                return fn;
            },

            "ID": function( id ) {
                var attrId = id.replace( runescape, funescape );
                return function( elem ) {
                    return elem.getAttribute( "id" ) === attrId;
                };

            }
        },
    }

    // 异常
    Sizzle.error = function( msg ) {
        throw new Error( "Syntax error, unrecognized expression: " + msg );
    }

    // 选择器缓存
    function createCache() {
        var keys = [];

        function cache(key, value) {
            if (keys.push(key) > Expr.cacheLength) {
                delete cache[keys.shift()];
            }
            return (cache[key] = value);
        }
        return cache;
    }

    Sizzle.select = function(selector) {
        var
            i,              // 计数器
            tokens,         // token序列
            token,          // token
            type,           // token类型：TAG, ID, CLASS, ATTR, CHILD, PSEUDO, NAME, 层级关系(>, +, 空格, ~)
            find,           // seed集合查询方法：getElementById、getElementsByTagName、getElementsByClassName
            seed,           // 种子集合：类型为ID、TAG、CLASS中任意一种的DOM元素集合
            match,          // 词法解析后的数据
            results = []    // 目标元素
            ;

        // 词法解析
        match = Sizzle.tokenize(selector);

        // 只有一组tokens的情况
        // 筛选出种子合集(seed)，重组css选择器
        if (match.length === 1) {
            tokens = match[0];
            i = tokens.length;

            // 通过遍历找出seed集合，顺序是从右往左
            while (i--) {
                token = tokens[i];

                // 如果是层级关系(>, +, 空格, ~)，跳出循环
                if (Expr.relative[(type = token.type)]) {
                    break;
                }

                // 如果是ID、TAG、CLASS中的一种
                if (find = Expr.find[type]) {
                    // 找到目标DOM元素
                    if (seed = find(token.matches[0])) {
                        // 从tokens中删除
                        tokens.splice(i, 1);
                        // 重组选择器
                        selector = seed.length && toSelector(tokens);
                        break;
                    }
                }
            }
        }

        var superMatcher = Sizzle.compile(selector, match);
        superMatcher(seed, results);

        return results;
    }

    // Token序列转css选择器字符串
    function toSelector( tokens ) {
        var i = 0,
            len = tokens.length,
            selector = "";
        for ( ; i < len; i++ ) {
            selector += tokens[ i ].value;
        }
        return selector;
    }

    // 预编译
    Sizzle.compile = function(selector, match) {
        var
            i,
            elementMatchers = [],
            cached = compilerCache[selector];

        if (!cached) {
            // match一般是有值的，所以这行if语句基本上是个摆设
            if (!match) {
                match = Sizzle.tokenize(selector);
            }

            i = match.length;
            while(i--) {
                cached = matcherFromTokens(match[i]);
                elementMatchers.push(cached);
            }
        }

        cached = compilerCache(
            selector,
            matcherFromGroupMatchers(elementMatchers)
        )

        return cached;
    }

    // 遍历Token序列生成匹配器
    function matcherFromTokens(tokens) {
        var
            i,
            token,
            matcher,
            matchers = []
            ;

        for (i = 0; i < tokens.length; i++) {
            token = tokens[i];

            if (matcher = Expr.relative[token.type]) { // 生成层级匹配器
                matchers = [addCombinator(elementMatcher(matchers), matcher)];
            } else {
                // 问题：为什么这里不写成matcher = Expr.filter[token.type](token.matches);
                // 因为ATTR类型的匹配器需要传入三个参数
                matcher = Expr.filter[token.type].apply(null, token.matches);
                matchers.push(matcher);
            }
        }

        return elementMatcher(matchers);
    }

    // 超级匹配器（多组）
    // 像div > p + .aaron[type="checkbox"], #id:first-child这种选择器有两组matcherFromTokens匹配器
    // 该方法的作用就是将两组matcherFromTokens匹配器合并成一个匹配器
    function matcherFromGroupMatchers(elementMatchers) {
        return function (seed, results) {
            var i,
                j,
                elems,      // 种子合集
                elem,       // 种子合集中的单个DOM元素
                matcher;    // matcherFromTokens匹配器

            // 如果没有种子元素则全文检索
            elems = seed || Expr.find["TAG"]("*");

            // 遍历所有元素
            for (i = 0; i < elems.length; i++) {
                j = 0;
                elem = elems[i];

                // 遍历所有matcherFromTokens匹配器
                // 把elems中的元素挨个放入elementMatchers匹配器中
                // 若返回为true，将该元素放入results集合中
                while (matcher = elementMatchers[j++]) {
                    if (matcher(elem)) {
                        results.push(elem);
                    }
                }
            }
        }
    }

    // 合并多个匹配器
    function elementMatcher( matchers ) {
        return matchers.length > 1 ?

            // 如果是多个匹配器
            function( elem, context, xml ) {
                var i = matchers.length;
                while ( i-- ) {
                    if ( !matchers[ i ]( elem, context, xml ) ) {
                        return false;
                    }
                }
                return true;
            } :

            // 如果是单个匹配器，返回自己即可
            matchers[ 0 ];
    }

    // 层级关系处理器
    function addCombinator(matcher, combinator) {
        var dir = combinator.dir;

        return combinator.first ?

            // 紧密型
            function( elem, context, xml ) {
                while ( ( elem = elem[ dir ] ) ) {

                    // 加这么一个判断是因为有的时候拿到的是text类型的元素
                    if ( elem.nodeType === 1 ) {
                        return matcher( elem, context, xml );
                    }
                }
                return false;
            } :

            // 非紧密型一直递归查询，查到最后为null会跳出循环并且返回false
            // 如果递归过程中某一层返回true
            function( elem, context, xml ) {
                while ( ( elem = elem[ dir ] ) ) {
                    if ( elem.nodeType === 1 ) {
                        if (matcher(elem, context, xml)) {
                            return true;
                        }
                    }
                }
                return false;
            }
    }

    // 获取元素属性值
    Sizzle.attr = function( elem, name ) {
        return elem.getAttribute( name );
    }

    window.Sizzle = Sizzle;
})(window);